package com.zhugang.week13.array;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: findClosest
 * @author: chanzhugang
 * @create: 2022/09/18 15:46
 */
public class FindClosest {

    /**
     * 面试题 17.11 单词距离
     * https://leetcode.cn/problems/find-closest-lcci/
     *
     * @param words
     * @param word1
     * @param word2
     * @return
     */
    public int findClosest(String[] words, String word1, String word2) {
        // 两个单词在数组中的位置分别放在两个数组中，求两个数组中的最小差(转为求面试题16.06 最小差)
        List<Integer> word1List = new ArrayList<>();
        List<Integer> word2List = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                word1List.add(i);
            }
            if (words[i].equals(word2)) {
                word2List.add(i);
            }
        }
        // 两个集合中的值是位置，已经是排好序的

        // 求两个集合最小差
        int i = 0;
        int j = 0;
        int min = Integer.MAX_VALUE;
        while (i < word1List.size() && j < word2List.size()) {
            if (word1List.get(i) > word2List.get(j)) {
                min = Math.min(min, word1List.get(i) - word2List.get(j));
                j++;
            } else {
                min = Math.min(min, word2List.get(j) - word1List.get(i));
                i++;
            }
        }
        return min;
    }

    // 代码简单：
    public int findClosest2(String[] words, String word1, String word2) {
        int start = -1;
        int end = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                start = i;
            }
            if (words[i].equals(word2)) {
                end = i;
            }
            if (start != -1 && end != -1) {
                // 满足的条件需要考虑下
                min = Math.min(min, Math.abs(end - start));
            }
        }
        return min;
    }
}